package com.zhang.sort.cmp;

import com.zhang.sort.Sort;

/**
 * @author 张吉鑫
 * @Description 快速排序
 * @date 2021/4/18 13:51
 */
public class QuickSort<E> extends Sort<E> {
    /**
     * 执行流程
     * ① 从序列中随机选择一个轴点元素（pivot）
     *   然后跟索引0位置的元素进行交换
     *   选择 0 位置的元素为轴点元素
     * ② 利用 pivot 将序列分割成 2 个子序列
     *   将小于 pivot 的元素放在pivot前面（左侧）
     *   将大于 pivot 的元素放在pivot后面（右侧）
     *   等于pivot的元素放哪边都可以
     * ③ 对子序列进行 ① ② 操作
     *   直到不能再分割（子序列中只剩下1个元素）
     */
    @Override
    protected void sort() {
        sort(0,array.length);
    }

    private void sort(int begin,int end){
        if (end - begin < 2){
            return;
        }
        int mid = pivotIndex(begin, end);
        sort(begin, mid);
        sort(mid + 1, end);
    }

    private int pivotIndex(int begin,int end){
        swap(begin, (int) (begin + Math.random() * (end - begin)));
        E pivot = array[begin];
        end--;

        while (begin < end){
            while (begin < end){
                if (cmpElement(array[end], pivot) > 0){
                    end--;
                }else {
                    array[begin++] = array[end];
                    break;
                }
            }
            while (begin < end){
                if (cmpElement(array[begin], pivot) < 0){
                    begin++;
                }else {
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        array[begin] = pivot;
        return begin;
    }

}
